/*
   生成1～8的序列，要求，每个数字在相应的位置仅出现一次且必须出现一次；
   同时，相邻的数字序列在之前未出现过，例如：在前面出现过1，2，后面则不允许出现1，2
*/

#include <stdio.h>
#include <assert.h>
#include <algorithm>

const int N = 8;

int mate[N][N] = {0};
void print()
{
    printf("Sequence:\n");
    for (int i = 0; i < N; i++) {
        for (int k = 0; k < N; k++)
            printf("%4d,", mate[i][k] + 1);
        printf("\n");
    }
}

bool placed_line[N][N] = {false};
bool placed_colm[N][N] = {false};
void print_placed(bool placed[N][N])
{
    for (int i = 0; i < N; i++) {
        printf("Line %d:", i);
        for (int k = 0; k < N; k++)
            printf("%3d", placed[i][k]);
        printf("\n");
    }
}
void place(int line, int colm)
{
    if (line >= N) {
        print();
        exit(0);
    }
    if (colm >= N) {
        // print();
        place(line + 1, 0);
        return;
    }
    for (int v = 0; v < N; v++) {
        // 判断在[line, colm]位置放置数字v
        // 判断数字v是否已经在第line行放置过
        if (placed_line[line][v]) {
            // print_placed(placed_line);
            // printf("%d is placed in this line(%d), colm=%d\n", v, line, colm);
            continue;
        }
        // 判断数字v是否已经在第colm列放置过
        if (placed_colm[v][colm]) {
            // print_placed(placed_colm);
            // printf("%d is placed in this column(%d), line=%d\n", v, colm, line);
            continue;
        }
        // 在前面的行查找是否存在相同的序列
        bool found = false;
        if (colm > 0) {
            for (int i = 0; i < line; i++) {
                for (int k = 0; k < N - 1; k++)
                        if (mate[i][k] == mate[line][colm - 1] && mate[i][k+1] == v) {
                            // printf("[%d,%d]\n", i, k);
                            found = true;
                        }
            }
        }
        if (!found) {
            placed_line[line][v] = true;
            placed_colm[v][colm] = true;
            mate[line][colm] = v;
            // printf("[%d, %d] = %d\n", line, colm, v);
            place(line, colm + 1);
            placed_line[line][v] = false;
            placed_colm[v][colm] = false;
        }
    }
}

int main()
{
    // 生成第一行
    for (int i = 0; i < N; i++) {
        mate[0][i] = i;
        placed_line[0][i] = true;
        placed_colm[i][i] = true;
    }
    place(1, 0);
}
